Abstract

Richard Hammack
More on direct product cancellation of graphs

Abstract. The direct (or tensor) product of graphs obeys a limited cancellation property. Lovász proved that if C has an odd cycle then A × C = B × C if and only if A = B, but cancellation can fail if C is bipartite. We investigate the ways cancellation can fail. Given a graph A and a bipartite graph C, we classify the graphs B for which A × C = B × C. Further, we give exact conditions on A that guarantee A × C = B × C implies A = B. Combined with Lovász’s result, this characterizes the situations in which cancellation holds or fails.